package com.notion.algorithms.datastructures;

public class BinarySearchTree<T extends Comparable<T>> {
	private Node<T> rootNode = null;

	public void insert(T element){
		if(null == rootNode){
			rootNode = new Node<T>(element);
		}
		else{
			traverseAndInsert(new Node<T>(element), rootNode);
		}
	}
	private void traverseAndInsert(Node<T> element,Node<T> currentNode){
		Node<T> child;
		if(element.compareTo(currentNode)>0){
			child = currentNode.getRightChild();
			if(null==child){
				currentNode.setRightChild(element);
			}
			else{
				traverseAndInsert(element, child);
			}
		}
		else{
			child = currentNode.getLeftChild();
			if(null==child){
				currentNode.setLeftChild(element);
			}
			else{
				traverseAndInsert(element, child);
			}
		}
	}
	public Node<T> search(T value){
		Node<T> node = null;
		if(rootNode != null){
			node = traverseAndSearch(value,rootNode);
		}
		return node;
	}
	private Node<T> traverseAndSearch(T value, Node<T> currentNode){
		Node<T> node = null;
		int comparedValue = value.compareTo(currentNode.getValue());
		if(0==comparedValue){
			node = currentNode;
		}
		else if(comparedValue>0){
			if(null!=currentNode.getRightChild()){
				node = traverseAndSearch(value, currentNode.getRightChild());
			}
		}
		else if(comparedValue<0){
			if(null!=currentNode.getLeftChild()){
				node = traverseAndSearch(value, currentNode.getLeftChild());
			}
		}
		return node;
	}
	private static class Node<T extends Comparable<T>> implements Comparable<Node<T>>{
		private T value;
		private Node<T> leftChild;
		private Node<T> rightChild;
		
		public Node(T value){
			this.value =  value;
		}

		public Node<T> getLeftChild() {
			return leftChild;
		}

		public void setLeftChild(Node<T> leftChild) {
			this.leftChild = leftChild;
		}

		public Node<T> getRightChild() {
			return rightChild;
		}

		public void setRightChild(Node<T> rightChild) {
			this.rightChild = rightChild;
		}

		public T getValue() {
			return value;
		}

		public int compareTo(Node<T> o) {
			return this.getValue().compareTo(o.getValue());
		}	
		
		@Override
		public boolean equals(Object obj) {
			boolean isEqual = false;
			if(obj instanceof Node){
				if(this.getValue().equals(((Node)obj).getValue())){
					isEqual = true;
				}
			}
			return isEqual;
		}
		@Override
		public String toString() {
			return "Node:"+getValue();
		}

	}

	public static void main(String[] args){
		BinarySearchTree<String> bst = new BinarySearchTree<String>();

		bst.insert("abcd");
		bst.insert("teee");
		bst.insert("zzzzs");
		System.out.println(bst.search("zzzzs"));

	}
}
